#include "heap.h"


/**
 * @brief 比较两个数大小
 * @param a 第一个数
 * @param b 第二个数
 * @retval 如果a>b,返回true,否则false 
*/
static bool cmp_max_int(const int a,const int b)
{
    if(a > b)
    {
        return true;
    }
    else 
    {
        return false;
    }
}


/**
 * @brief 比较两个数大小
 * @param a 第一个数
 * @param b 第二个数
 * @retval 如果a<b,返回true,否则false 
*/
static bool cmp_min_int(const int a,const int b)
{
    if(a < b)
    {
        return true;
    }
    else 
    {
        return false;
    }
}

/**
 * @brief 用于互换两个地址的内容
 * @param a 地址1
 * @param b 地址2
 * @retval None
*/
static void swap_int(int *const a,int *const b)
{
    int temp;

    temp = *a;
    *a = *b;
    *b = temp; 
}


/**
 * @brief 虚函数,比较大小
 * @param zs 堆指针
 * @param a 第一个数
 * @param b 第二个数
 * @retval 
*/
static inline bool heap_cmp_int(heap_t zs,int a,int b)
{
    return zs->vptr->cmp_int(a,b);
}

/**
 * @brief 堆初始化
 * @param zs 堆指针
 * @param capacity 最大容量
 * @param data 数据存储地址
 * @retval None
*/
static void heap_init(heap_t zs,int capacity,int *data)
{
    zs->data = data;
    zs->capacity = capacity;
    zs->size = 0;
}


/**
 * @brief 初始化为小根堆
 * @param zs 堆指针
 * @param capacity 最大容量
 * @param data 数据存储地址
 * @retval None
*/
void heap_min_init(heap_t zs,int capacity,int *data)
{
    //虚函数表
    static struct{
        bool (*cmp_int)(int,int);
    }vtbl = {
        .cmp_int = cmp_min_int,
    };

    heap_init(zs,capacity,data);
    zs->vptr = (void *)&vtbl;
}


/**
 * @brief 初始化为大根堆
 * @param zs 堆指针
 * @param capacity 最大容量
 * @param data 数据存储地址
 * @retval None
*/
void heap_max_init(heap_t zs,int capacity,int *data)
{
    //虚函数表
    static struct{
        bool (*cmp_int)(int,int);
    }vtbl = {
        .cmp_int = cmp_max_int,
    };

    heap_init(zs,capacity,data);
    zs->vptr = (void *)&vtbl;
}


/**
 * @brief 建堆
 * @param zs 堆指针
 * @param arr 数组首地址
 * @param size 数组大小
 * @param init 根据是建立大(小)根堆
 *  选择为heap_max_init还是heap_min_init
 * @retval None
*/
void heap_build(heap_t zs,int *arr,int size,void (*init)(heap_t,int,int *))
{
    int i;

    init(zs,size,arr);
    zs->size = size;

    for(i = heap_index_parent(size - 1);i >= 0;i--)
    {
        heap_adjust_down(zs,i);
    }
}


/**
 * @brief 堆元素向下调整(下滤)
 * @param zs 堆指针
 * @param index 元素下标
 * @retval None
*/
void heap_adjust_down(heap_t zs,int index)
{
    int child;

    child = heap_index_left(index);

    while(child < zs->size)
    {
        if(heap_cmp_int(zs,zs->data[child + 1],zs->data[child]) && child + 1 < zs->size)
        {
            child++;
        }

        if(heap_cmp_int(zs,zs->data[child],zs->data[index]))
        {
            swap_int(zs->data + index,zs->data + child);
        }
        else 
        {
            break;
        }

        index = child;
        child = heap_index_left(index);
    }
}


/**
 * @brief 堆元素向上调整(上滤)
 * @param zs 堆指针
 * @param index 元素下标
 * @retval None
*/
void heap_adjust_up(heap_t zs,int index)
{
    int parent;

    parent = heap_index_parent(index);

    while(parent >= 0)
    {
        if(heap_cmp_int(zs,zs->data[index],zs->data[parent]))
        {
            swap_int(zs->data + parent,zs->data + index);
        }
        else 
        {
            break;
        }
        index = parent;
        parent = heap_index_parent(index);
    }
}


/**
 * @brief 遍历堆
 * @param zs 堆指针
 * @param look 打印一个整数的函数指针
 * @retval None
*/
void heap_trav(heap_t zs,void (*look)(int))
{
    for(int i = 0;i < zs->size;i++)
    {
        look(zs->data[i]);
    }
}


/**
 * @brief 插入堆
 * @param zs 堆指针
 * @param data 数据
 * @retval None
*/
void heap_insert(heap_t zs,int data)
{
    if(zs->size < zs->capacity)
    {
        zs->data[zs->size++] = data;
        heap_adjust_up(zs,zs->size - 1);
    }
}


/**
 * @brief 弹出堆
 * @param zs 堆指针
 * @retval 弹出的元素
*/
int heap_pop(heap_t zs)
{
    int temp;

    if(zs->size == 0)
    {
        return 0;
    }

    temp = zs->data[0];
    zs->data[0] = zs->data[--zs->size];

    heap_adjust_down(zs,0);

    return temp;
}



